package com.sourcetrip.raw.adt;


import com.sourcetrip.raw.adt.abs.MyAbstractBBST;
import com.sourcetrip.raw.model.Color;
import com.sourcetrip.raw.model.MyBinaryNode;
import com.sourcetrip.raw.model.MyRBNode;

/**
 * @author: ZhouBert
 * @date: 2020/12/1
 * @description: AVL-Tree 和 RB-Tree 都有相同的旋转逻辑
 * <p>
 * 红黑树的判断条件最好跟颜色挂钩！
 * 用颜色判断来替代 是否有子节点之类的
 */
public class MyRedBlackTree<E extends Comparable> extends MyAbstractBBST<E> {


	/**
	 * 首先攻克 add()
	 * 这次纯粹只是写个注释
	 * --
	 * 心中有 b-tree
	 * 1.b-tree 中，新元素必然添加到 叶子节点中；
	 * 2.新添加的元素默认为红色，因为这样在红黑树的性质中，除了 Red 子节点 != Red 以外其他都能满足；这是为了尽快满足红黑树的性质；
	 * 但是如果添加的是根节点（size==0 时），才需要染黑。
	 * 3.对添加的情况进行讨论：
	 * -1-父节点是 BLACK
	 * -2-
	 *
	 * @param element
	 */
	@Override
	public void add(E element) {
		super.add(element);
	}


	@Override
	public void clear() {

	}


	/**
	 * B树中，真正被删除的元素，在 叶子节点中
	 * 也就是说，在红黑树中，真正被删除发生在最后一层
	 *
	 * @param element
	 */
	@Override
	public void remove(E element) {

	}

	@Override
	public boolean contains(E element) {
		return false;
	}


	/**
	 * 红黑树添加节点后调整的 关键方法！
	 * 1.添加的是根节点
	 * 2.p 黑
	 * 3.uncle 红色
	 * 4.uncle 不为红色
	 *
	 * @param node 添加的节点
	 */
	@Override
	protected void afterAdd(MyBinaryNode<E> node) {
//		if (size == 1) {
//			//如果添加的是根节点
//			black(root);
//			return;
//		}
		//如果添加的是根节点 -已经包括了上溢的情况！
		MyBinaryNode<E> parent = node.getParent();
		if (parent == null) {
			black(root);
			return;
		}
		//1.parent.color == BLACK (4种情况)
		if (colorOf(parent) == Color.BLACK) {
			//直接添加不处理
			return;
		}
		// 祖父节点
		MyBinaryNode<E> grand = parent.getParent();
		// 叔叔节点
		MyRBNode uncle = sibling(parent);
		//2.parent.color == RED && parent.uncle.color == BLACK
		if (colorOf(uncle) == Color.BLACK) {
			//此时需要进行旋转
			//2.1	L
			if (parent.isLeftChild()) {
				if (node.isLeftChild()) {
					//LL
					//1.parent -> BLACK
					//2.grand -> RED
					//3.grand 右旋转
					black(parent);
					red(grand);
					rotateRight(grand);
				} else {
					//LR
					//1.node -> BLACK
					//2.grand -> RED
					//3.parent 左旋；grand 右旋
					black(node);
					red(grand);
					rotateLeft(parent);
					rotateRight(grand);
				}
			} else {
				// 上溢
				//R
				if (node.isLeftChild()) {
					//RL
					//1.node -> BLACK
					//2.grand -> RED
					//3.parent 右旋；grand 左旋
					black(node);
					red(grand);
					rotateRight(parent);
					rotateLeft(grand);
				} else {
					//RR
					//1.parent -> BLACK
					//2.grand -> RED
					//3.grand 左旋转
					black(parent);
					red(grand);
					rotateLeft(grand);
				}
			}
		} else {
			//3.parent.color == RED && parent.uncle.color == RED
			//将 parent uncle 染色
			black(parent);
			black(uncle);
			//将 grand 染红
			red(grand);
			//作为一个新的节点添加到 上一层-> 重新调整
			afterAdd(grand);
			//此时如果 根节点不再是 BLACK 进行染色
//			if (colorOf(root) == Color.RED) {
//				black(root);
//			}
		}
	}

	/**
	 * 对于删除节点之后的调节处理
	 * 分情况讨论：
	 * 1.删除的是 RED 节点：不做任何调整；
	 * 2.删除的是 BLACK 节点:
	 * -1-度为2 的 BLACK 节点:不存在，不会被删除，因为会被值覆盖，实际删除的是前驱或者后继；
	 * -2-拥有一个 RED 子节点的 BLACK 节点
	 * 从B-Tree 的角度来看，剩下的一个节点可以成为一个新的节点 -> BLACK
	 *
	 * @param deletedNode 被删除的节点（通过保留对 parent 的引用来实现调整）
	 */
	@Override
	protected void afterRemove(MyBinaryNode<E> deletedNode, MyBinaryNode<E> replaceNode) {
		if (colorOf(deletedNode) == Color.RED) {
			//如果删除的是红色的 -> 直接删除
			return;
		}
		//判断顶替删除位置的节点是否为 RED
		//但是想要达到这个判断，只有一个 deleteNode 是不够的！！！于是修改了传参，增加了一个替代节点
		//此时，删除的节点为黑色
		if (colorOf(replaceNode) == Color.RED) {
			//1.replace -> BLACK
			black(replaceNode);
			return;
		}
		MyBinaryNode<E> parent = deletedNode.getParent();
		//最复杂的是删除 黑色叶子节点的情况！
		//1.如果删除的是根节点
		if (parent == null) {
			return;
		}
		//2.删除的是黑色叶子节点【下溢】
		boolean left = parent.getLeft() == null || deletedNode.isLeftChild();
		MyBinaryNode sibling = left ? parent.getRight() : parent.getLeft();
		if (left) {
			if (isRed(sibling)) {
				black(sibling);
				red(parent);
				rotateLeft(parent);
				//这里跟下面一种情况是有重复的，所以先做这里的，然后可以达到复用的
				sibling = parent.getRight();
			}

			//2.1 兄弟节点必然是黑色的
			if (isBlack(sibling.getLeft()) && isBlack(sibling.getRight())) {
				isBlack(parent);
			}
		}
	}

	/**
	 * 创建节点（默认红色）
	 *
	 * @param ele
	 * @param parent
	 * @return
	 */
	@Override
	protected MyRBNode<E> createNode(E ele, MyBinaryNode<E> parent) {
		MyRBNode<E> node = new MyRBNode<>(ele, parent, Color.RED);
		return node;
	}

//region	辅助函数


	/**
	 * 染色
	 *
	 * @param node
	 * @param color
	 * @return
	 */
	private MyRBNode<E> color(MyBinaryNode<E> node, int color) {
		if (node == null) return ((MyRBNode) node);
		((MyRBNode) node).setColor(color);
		return ((MyRBNode) node);
	}

	/**
	 * 染红色
	 *
	 * @param node
	 * @return
	 */
	private MyRBNode<E> red(MyBinaryNode<E> node) {
		((MyRBNode) node).setColor(Color.RED);
		return ((MyRBNode) node);
	}

	/**
	 * 黑色
	 *
	 * @param node
	 * @return
	 */
	private MyRBNode<E> black(MyBinaryNode<E> node) {
		((MyRBNode) node).setColor(Color.BLACK);
		return ((MyRBNode) node);
	}

	/**
	 * 返回一个节点的颜色
	 *
	 * @param node
	 * @return null 节点返回黑色
	 */
	private int colorOf(MyRBNode<E> node) {
		if (node == null) return Color.BLACK;
		return node.getColor();
	}

	/**
	 * 返回一个节点的颜色
	 *
	 * @param node
	 * @return
	 */
	private int colorOf(MyBinaryNode<E> node) {
		return colorOf((MyRBNode<E>) node);
	}

	/**
	 * 判断节点是否为红色
	 *
	 * @param node
	 * @return
	 */
	private boolean isRed(MyBinaryNode<E> node) {
		if (node == null) return false;
		return ((MyRBNode) node).getColor() == Color.RED;
	}

	/**
	 * 判断节点是否为黑色
	 *
	 * @param node
	 * @return
	 */
	private boolean isBlack(MyBinaryNode<E> node) {
		if (node == null) return true;
		return ((MyRBNode) node).getColor() == Color.BLACK;
	}

	/**
	 * 获取该节点的叔叔节点
	 *
	 * @param node
	 * @return
	 */
	private MyRBNode sibling(MyBinaryNode<E> node) {
		MyBinaryNode uncle = ((MyRBNode) node).sibling();
		return (MyRBNode) uncle;
	}

	/**
	 * 左旋转
	 *
	 * @param grand
	 */
	private void rotateLeft(MyBinaryNode<E> grand) {
		MyBinaryNode<E> parent = grand.getRight();
		MyBinaryNode<E> child = parent.getLeft();
		grand.setRight(child);
		parent.setLeft(grand);
		afterRotate(grand, parent, child);
	}

	/**
	 * 右旋转
	 *
	 * @param grand
	 */
	private void rotateRight(MyBinaryNode<E> grand) {
		MyBinaryNode<E> parent = grand.getLeft();
		MyBinaryNode<E> child = parent.getRight();
		grand.setLeft(child);
		parent.setRight(grand);
		afterRotate(grand, parent, child);
	}

	private void afterRotate(MyBinaryNode<E> grand, MyBinaryNode<E> parent, MyBinaryNode<E> child) {
		MyBinaryNode<E> ggrand = grand.getParent();
		if (ggrand != null) {
			if (grand.isLeftChild()) {
				ggrand.setLeft(parent);
			} else {
				ggrand.setRight(parent);
			}
		}
		parent.setParent(ggrand);
		grand.setParent(parent);
		if (child != null) {
			child.setParent(grand);
		}

	}

	//endregion
}
